(1) Field of the Invention
The present invention relates to an apparatus for representing curved surfaces in computer graphics, and particularly to a curved surface subdivision apparatus for performing subdivision processing on curved surfaces for polygonal approximations thereof.
(2) Description of the Related Art
In recent years, computer graphics (hereinafter referred to as “CG”) has been indispensable as one type of an image production technique. In modeling that is an important constituent technology in the field of CG, representation of an object by use of a set of polygons is the most popular technique for object rendering. However, with the advances in the CG technology, object rendering in various forms has been in increasing demand. Object rendering by use of parametric surfaces such as NURBS surfaces and Bezier surfaces is a typical example. Generally speaking, an object represented by such parametric surfaces has advantages over an object represented by a set of polygons, in that the former is more compact in an amount of data and has a higher affinity for data transmission via a network such as a LAN and the Internet.
FIG. 1 shows an example of an order 4 (a degree 3) rational Bezier surface that is a typical parametric surface. An order 4 (a degree 3) rational Bezier surface is expressed by the following equation:                                           B            ⁡                          (                              u                ,                v                            )                                =                                                    UMQM                T                            ⁢              V                        =                                          UM                ⁡                                  [                                                                                                              Q                          00                                                                                                                      Q                          01                                                                                                                      Q                          02                                                                                                                      Q                          03                                                                                                                                                              Q                          10                                                                                                                      Q                          11                                                                                                                      Q                          12                                                                                                                      Q                          13                                                                                                                                                              Q                          20                                                                                                                      Q                          21                                                                                                                      Q                          22                                                                                                                      Q                          23                                                                                                                                                              Q                          30                                                                                                                      Q                          31                                                                                                                      Q                          32                                                                                                                      Q                          33                                                                                                      ]                                            ⁢                              M                T                            ⁢              V                                      ⁢                                  ⁢                  M          =                      [                                                                                -                    1                                                                    3                                                                      -                    3                                                                    1                                                                              3                                                                      -                    6                                                                    3                                                  0                                                                                                  -                    3                                                                    3                                                  0                                                  0                                                                              1                                                  0                                                  0                                                  0                                                      ]                          ,                  U          =                      [                                                                                u                    3                                                                                        u                    2                                                                    u                                                  1                                                      ]                          ,                  V          =                                    [                                                                                          v                      3                                                                                                  v                      2                                                                            v                                                        1                                                              ]                        T                                              Equation        ⁢                                  ⁢        1            
A rational Bezier surface is expressed by use of two independent parameters. In this example, the first and second axis directions of a plane expressed by these parameters that define the curved surface shall be a u direction and a v direction respectively, for example. It should be noted that 0<=u<=1 and 0<=v<=1 hold in this example. Qij (i=0, . . . , 3, j=0 , . . . , 3) are control points that define a shape of a rational Bezier surface, and an order 4 (a degree 3) Bezier surface is defined by a grid of 4×4=16 control points.
Among these control points, Q00, Q30, Q03, Q33 are located on the surface but other points are located out of the surface. Each control point includes a w component corresponding to weight in addition to x, y and z components indicating the location of the point. Weight is an index indicating strength of influence that each control point has on a shape of a Bezier surface. It is often convenient to use quartic (degree 4) homogeneous coordinate representation in order to handle these components in an unified manner. There are relations X=w*x, Y=w*y, Z=w*z and W=w between the components X, Y, Z and W expressed in the homogeneous coordinate and the components x, y, z and w, where * indicates a multiplication.
In addition, it is known that a Bezier surface has convex hull property and thus the surface is completely contained in a polyhedron that is formed by control points.
For high-speed hardware rendering of an object represented by parametric surfaces, approximation of the object as polygonal models is very effective. Such approximation of the object is achieved by calculating points located on each surface based on control points and connecting these points. A Bezier surface has a property that the points obtained by calculating the points that split distances between neighboring control points are located on the surface (which will be described in detail later). As for a conventional technique for processing curved surface graphics by use of this property, see, for example, Japanese Laid-Open Patent Application No. 2001-331812 Publication “Graphic Information Generation Apparatus, Image Processing Apparatus, Information Processing Apparatus, Graphic Information Generation Method and Storage Medium”, p. 7–p. 11.
In the above conventional technology, a linear interpolation unit is provided. When generating vertex values for representing a curved surface graphics based on a grid of control points that define the shape of the surface, this linear interpolation unit calculates, in sequence, A×(1−t)+B×t for a coordinate value of a new control point that splits a distance between neighboring control points, where A and B are the neighboring control points of predetermined bit width and t is an interpolation coefficient having a value of 0≦t≦1 of predetermined bit width. Then, the linear interpolation unit calculates new control points between neighboring control points in sequence so as to finally obtain the coordinate values of the vertices for representing the curved surface graphics. It also calculates a lot of coordinate values for representing the curved surface graphics by updating the value of the interpolation coefficient t.
However, according to the above-mentioned conventional technology, since the graphic information generation unit needs to control not only input and output of control points but also update of the interpolation coefficient t, for example, keeping the current value thereof during a series of processing and updating the value after the processing, the structure of the linear operation unit is complex. Therefore, how to reduce an amount of operation is a problem in representation of curved surface images.
In addition, in order to represent a three-dimensional (3D) object in more detail and realistically, the number of subdivisions of polygons must be increased inevitably for approximation of curved surfaces, and thus there is a problem of increase in calculation load.